
\prob{008A}{赛事矛盾}

若在某场赛事中，有$n$位参赛选手，每两位选手赛一场，不存在平局。若对于任意$k$位选手，都存在一位选手（不在这$k$位中），使得这$k$位选手均被该选手击败，则称该赛事结果是$k$矛盾的。

求证：已知一正整数$k$，则对于所有参赛选手数量$n$满足
\[ n^k\left(1 - 2^{-k}\right)^{n - k} < k! \]
的赛事，都存在$k$矛盾的比赛结果。
\problabels{yellow/数学谜题, green/证明题}

\subsection{概率论}

不妨随机决定比赛结果，然后考虑比赛结果非$k$矛盾的概率。

将$n$位选手命名为$C_1, C_2, C_3, \dots, C_n$。考虑选手集合$C = \{C_1, C_2, C_3, \dots, C_n\}$的某个基数为$k$的子集$K_i$，令事件$E_i$为“$K_i$中的这$k$位选手没有被其他$n - k$位选手中的任意一个全部击败”，事件$E$为“比赛结果非$k$矛盾”，则可知
\[ E = E_1 \cup E_2 \cup E_3 \cup E_4 \cup \dots \cup E_{c - 1} \cup E_c \]
考虑到基数为$n$的集合$C$有$C_n^k$个基数为$k$的集合$K$，故$c = C_n^k$。

对于某个$K_i$，考虑在$C$中而不在$K_i$中的某个选手$C_j$，由于比赛结果是随机的，所以$C_j$击败$K_i$中所有选手的概率为$(1/2)^k = 2^{-k}$，故其互补事件“$C_j$未击败$K_i$中所有选手”的概率为$1 - 2^{-k}$。这样的选手$C_j$共$n - k$个，故可知事件$E_i$的概率为
\[ P(E_i) = \left(1 - 2^{-k}\right)^{n - k} \]
于是
\begin{align*}
  & P(E) \\
  ={}& P(E_1 \cup E_2 \cup E_3 \cup E_4 \cup \dots \cup E_{c - 1} \cup E_c) \\
  \le{}& P(E_1) + P(E_2) + P(E_3) + \dots + P(E_c) \\
  ={}& c\left(1 - 2^{-k}\right)^{n - k} = C_n^k\left(1 - 2^{-k}\right)^{n - k} \\
  ={}& \frac{n!}{k!(n - k)!}\left(1 - 2^{-k}\right)^{n - k} \\
  ={}& \frac{n(n - 1)(n - 2)\cdots(n - k + 1)}{k!}\left(1 - 2^{-k}\right)^{n - k} \\
  <{}& \frac{n^k}{k!}\left(1 - 2^{-k}\right)^{n - k} < 1 \\
\end{align*}
故其互补事件“比赛结果是$k$矛盾”的概率不为0，即其有可能发生，故存在$k$矛盾的比赛结果。证毕。
